package writtenTraining.day22;

import java.util.*;

/**
 * day22;(1)贪心：[编程题]添加字符
 */

public class Main {
    public static void main(String[] args) {
        // 贪心 + 偏移对比

        // 输入数据
        Scanner in = new Scanner(System.in);
        char[] a = in.next().toCharArray(), 
        b = in.next().toCharArray();

        // 偏移统计
        int k = b.length - a.length, ret = 0x3f3f3f3f;
        for(int i = 0; i <= k; i++) {
            int count = 0;
            for(int j = 0; j < a.length; j++) {
                // 统计该位置不想等的个数
                if(a[j] != b[j+i]) {
                    count++;
                }
            }

            // 更新最小不想等的个数
            ret = Math.min(ret, count);
        }


        // 输出结果
        System.out.println(ret);
    }
}

/**
 * day22:(2)贪心+ 位运算：[编程题]数组变换
 */


 class Main1 {
    public static void main(String[] args) {
        // 贪心 + 位运算


        // 输入数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] nums = new long[n];
        long maxNum = 0L;
        for(int i =0; i < n; i++) {
            nums[i] = in.nextLong();
            maxNum = Math.max(nums[i], maxNum);
        }

        for(int i = 0; i < n; i++) {
            if(maxNum % nums[i] != 0) {
                System.out.println("NO");
                return;
            } else {
                if(!checkNum(maxNum / nums[i])) {
                    System.out.println("NO");
                    return;
                }
            }
        }

        // 用最大数去除，判断是否是 2 的次方幂
        System.out.println("YES");

    }

    private static boolean checkNum(long num) {
        int ret = 0;
        // 从1 开始统计个数是否为 1
        // 如果1 出现的个数为 1个就说明是2 的次方幂

        for(int i = 0; i < 64; i++) {
            if(((1L << i) & num) != 0) {
                ret++;
            }
        }

        return ret == 1;
    }
}



/**
 * day22:(3)动态规划 + 01背包：[NOIP2001]装箱问题
 */


class Main2 {
    public static void main(String[] args) {
//         动态规划 + 01背包

        // 输入数据
        Scanner in = new Scanner(System.in);
        int maxV = in.nextInt(), n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n ; i++) {
            nums[i] = in.nextInt();
        }

//         创建 dp
        int[][] dp = new int[n+1][maxV + 1];
//         初始化
//         填表
        for(int i  = 1; i <= n; i++) {
            for(int j = 1; j <= maxV; j++) {
                // 继承前面的价值
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i-1][j-nums[i-1]] + nums[i-1]);
                }
            }
        }
//         返回值
        System.out.println(maxV - dp[n][maxV]);
    }
}


/**
 * day22:(3)动态规划 + 01背包 + 空间优化：[NOIP2001]装箱问题
 */



 class Main3 {
    public static void main(String[] args) {
//         动态规划 + 01背包 + 空间优化

        // 输入数据
        Scanner in = new Scanner(System.in);
        int maxV = in.nextInt(), n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n ; i++) {
            nums[i] = in.nextInt();
        }

//         创建 dp
        int[] dp = new int[maxV + 1];
//         初始化
//         填表
        for(int i  = 1; i <= n; i++) {
            for(int j = maxV; j >= nums[i-1] ; j--) {
                // 继承前面的价值
                dp[j] = Math.max(dp[j],
                        dp[j-nums[i-1]] + nums[i-1]);
//                 System.out.println(dp[j]);
            }
        }
//         返回值
        System.out.println(maxV - dp[maxV]);
    }
}